package lc;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Q451 {

    public String frequencySort(String s) {
        int[] ints = new int[123];
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            ints[aChar] ++;
        }
        // 创建一个桶
        StringBuilder[] bucket = new StringBuilder[s.length() + 1];
        for (int i = 0; i < bucket.length; i++) {
            bucket[i] = new StringBuilder();
        }
        // 记录从最小到最大所有的值
        for (int i = 0; i < ints.length; i++) {
            if (ints[i] != 0) {
                for (int j = 0; j < ints[i]; j++) {
                    bucket[ints[i]].append((char) i);
                }
            }
        }
        // 记得排序
        StringBuilder sb = new StringBuilder();
        for (int i = bucket.length - 1; i >= 1; i--) {
            sb.append(bucket[i]);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Q451 q451 = new Q451();
        System.out.println(q451.frequencySort("loveleetcode"));
    }
}
